今天是練習cpe的All You Need Is Love題目

程式碼

#include <bits/stdc++.h>
using namespace std;
int gcd(int x, int y)
{
	while((x%=y) && (y%=x))
	{
	}
	return x+y;
}
int num=1;
int main() 
{
	int N;
	string S ,L;
	cin >> N;
	
	while(N--)
	{
		cin >> S >> L;
		int s1=0;
		int s2=0;
		for(int i = 0 ;i<S.length();i++)
		{
			s1 *= 2;
			s1 += S[i] - '0';
		}
		for(int i = 0 ;i<L.length();i++)
		{
			s2 *= 2;
			s2 += L[i] - '0';
		}

		cout << "Pair #" << num++ << ": ";
		if(gcd(s1 ,s2) > 1)
		{
			cout << "All you need is love!" << endl;
		}
		else
		{
			cout << "Love is not all you need" << endl;	
		}
	}
    return 0;
}

解題方向

int gcd(int x, int y)
{
	while((x%=y) && (y%=x))
	{
	}
	return x+y;
}

• 一直用大數除小數取餘數。當其中一個變成0時，另一個就是GCD。

        int s1=0;
		int s2=0;
		for(int i = 0 ;i<S.length();i++)
		{
			s1 *= 2;
			s1 += S[i] - '0';
		}
		for(int i = 0 ;i<L.length();i++)
		{
			s2 *= 2;
			s2 += L[i] - '0';
		}

• 將二進位字串轉成十進位數字
• if(gcd(s1 ,s2) > 1) -> 若兩數的最大公因數（GCD）> 1表示它們有共同因子